home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 3: CDPD 3 / Almathera Ten on Ten - Disc 3: CDPD3.iso / scope / 176-200 / scopedisk192 / unzipv3.1 / unshrink.c < prev    next >
Text File  |  1995-03-19  |  4KB  |  153 lines
  1. /* ------------------------------------------------------------- */
  2. /*
  3.  * Shrinking is a Dynamic Ziv-Lempel-Welch compression algorithm
  4.  * with partial clearing.
  5.  *
  6.  */
  7.  
  8. void partial_clear()
  9. {
  10.     register int pr;
  11.     register int cd;
  12.  
  13.     /* mark all nodes as potentially unused */
  14.     for (cd = first_ent; cd < free_ent; cd++)
  15.         prefix_of[cd] |= 0x8000;
  16.  
  17.     /* unmark those that are used by other nodes */
  18.     for (cd = first_ent; cd < free_ent; cd++) {
  19.         pr = prefix_of[cd] & 0x7fff;    /* reference to another node? */
  20.         if (pr >= first_ent)            /* flag node as referenced */
  21.             prefix_of[pr] &= 0x7fff;
  22.     }
  23.  
  24.     /* clear the ones that are still marked */
  25.     for (cd = first_ent; cd < free_ent; cd++)
  26.         if ((prefix_of[cd] & 0x8000) != 0)
  27.             prefix_of[cd] = -1;
  28.  
  29.     /* find first cleared node as next free_ent */
  30.     cd = first_ent;
  31.     while ((cd < maxcodemax) && (prefix_of[cd] != -1))
  32.         cd++;
  33.     free_ent = cd;
  34. }
  35.  
  36.  
  37. /* ------------------------------------------------------------- */
  38.  
  39. void unShrink()
  40. {
  41. #define  GetCode(dest) READBIT(codesize,dest)
  42.  
  43.     register int code;
  44.     register int stackp;
  45.     int finchar;
  46.     int oldcode;
  47.     int incode;
  48.  
  49.  
  50.     /* decompress the file */
  51.     maxcodemax = 1 << max_bits;
  52.     codesize = init_bits;
  53.     maxcode = (1 << codesize) - 1;
  54.     free_ent = first_ent;
  55.     offset = 0;
  56.     sizex = 0;
  57.  
  58.     for (code = maxcodemax; code > 255; code--)
  59.         prefix_of[code] = -1;
  60.  
  61.     for (code = 255; code >= 0; code--) {
  62.         prefix_of[code] = 0;
  63.         suffix_of[code] = code;
  64.     }
  65.  
  66.     GetCode(oldcode);
  67.     if (zipeof)
  68.         return;
  69.     finchar = oldcode;
  70.  
  71.     OUTB(finchar);
  72.  
  73.     stackp = hsize;
  74.  
  75.     while (!zipeof) {
  76.         GetCode(code);
  77.         if (zipeof)
  78.             return;
  79.  
  80.         while (code == clear) {
  81.             GetCode(code);
  82.             switch (code) {
  83.  
  84.             case 1:{
  85.                     codesize++;
  86.                     if (codesize == max_bits)
  87.                         maxcode = maxcodemax;
  88.                     else
  89.                         maxcode = (1 << codesize) - 1;
  90.                 }
  91.                 break;
  92.  
  93.             case 2:
  94.                 partial_clear();
  95.                 break;
  96.             }
  97.  
  98.             GetCode(code);
  99.             if (zipeof)
  100.                 return;
  101.         }
  102.  
  103.  
  104.         /* special case for KwKwK string */
  105.         incode = code;
  106.         if (prefix_of[code] == -1) {
  107.             stack[--stackp] = finchar;
  108.             code = oldcode;
  109.         }
  110.  
  111.  
  112.         /* generate output characters in reverse order */
  113.         while (code >= first_ent) {
  114.             stack[--stackp] = suffix_of[code];
  115.             code = prefix_of[code];
  116.         }
  117.  
  118.         finchar = suffix_of[code];
  119.         stack[--stackp] = finchar;
  120.  
  121.  
  122.         /* and put them out in forward order, block copy */
  123.         if ((hsize-stackp+outcnt) < OUTBUFSIZ) {
  124.             zmemcpy(outptr,&stack[stackp],hsize-stackp);
  125.             outptr += hsize-stackp;
  126.             outcnt += hsize-stackp;
  127.             stackp = hsize;
  128.         }
  129.  
  130.         /* output byte by byte if we can't go by blocks */
  131.         else while (stackp < hsize)
  132.             OUTB(stack[stackp++]);
  133.  
  134.  
  135.         /* generate new entry */
  136.         code = free_ent;
  137.         if (code < maxcodemax) {
  138.             prefix_of[code] = oldcode;
  139.             suffix_of[code] = finchar;
  140.  
  141.             do
  142.                 code++;
  143.             while ((code < maxcodemax) && (prefix_of[code] != -1));
  144.  
  145.             free_ent = code;
  146.         }
  147.  
  148.         /* remember previous code */
  149.         oldcode = incode;
  150.     }
  151. }
  152.  
  153.